#include<vector>
#include<unordered_map>
#include<string>
using namespace std;
class Solution {
private:
    unordered_map<string, vector<int>> map;


    bool isOps(const string& input, int index) {
        return input[index] == '*' || input[index] == '-' || input[index] == '+';
    }

public:
    vector<int> diffWaysToCompute(string input) {
        if (map.find(input) != map.end())
            return map[input];
        int index = 0;
        while (index < input.size()) {
            if (isOps(input, index))
                break;
            ++index;
        }
        vector<int> res;
        if (index == input.size()) {
            res.push_back(atoi(input.c_str()));
        }
        else {
            for (index = 0; index < input.size(); ++index) {
                if (!isOps(input, index))
                    continue;
                auto res1 = diffWaysToCompute(input.substr(0, index));
                auto res2 = diffWaysToCompute(input.substr(index + 1, input.size() - index - 1));
                for (int i = 0; i < res1.size(); ++i) {
                    for (int j = 0; j < res2.size(); ++j) {
                        int val = res1[i];
                        switch (input[index]) {
                        case '-':val -= res2[j]; break;
                        case '+':val += res2[j]; break;
                        case '*':val *= res2[j]; break;
                        }
                        res.push_back(val);
                    }
                }
            }
        }
        map[input] = res;
        return res;

    }
};